\section{Problema 2}

\subsection{Enunciado}
Se tienen $n$ sensores identificados con los índices del 1 al $n$. El sensor $i$ mide a intervalos regulares de
$m_i$ minutos y todas las mediciones son registradas y almacenadas por orden de aparición. Si dos o más
sensores miden al mismo tiempo, el orden de almacenamiento de estas mediciones es por orden del índice
de los sensores que midieron. En el minuto 0 todos los sensores miden.
Se sabe que hubo un error en la $k$-ésima medición y se desea saber a qué sensor corresponde la misma.
Escribir un algoritmo que resuelva este problema con una complejidad temporal estrictamente mejor
que $O(kn)$.

\subsection{Introducci\'on}

Se nos pide que, dada una lista de sensores que miden a intervalos regulares, devolver el sensor que se encuentra en
en la $k$-ésima posición de la lista ordenada por orden de aparición.

Para resolver el problema planteamos la idea de ir manteniendo los sensores ordenados en un heap que representaría un
segmento dentro de la lista final ordenada por orden de aparición. Para lograr esto este heap se mentendría ordenado
por el tiempo de la próxima ejecución de cada sensor y, en caso de que dos sensores en un momento dado compartan el
mismo tiempo de próxima ejecución, se los ordenaría por su índice dentro de la lista inicial.

De esta forma se iría moviendo dicho segmento iterando hasta llegar a $k$.Por cada una de esas iteraciones se quita
del heap el sensor más próximo a medir y se lo volvería insertar con su tiempo de próxima medición modificado, sumandole
su intervalo.

Al final de la $k$-ésima iteración el sensor que quedaría como mínimo en el heap sería el $k$-ésimo sensor en la lista
ordenada por orden de aparición.

\subsection{Correctitud}
Como en cada iteración siempre se saca el mínimo del heap (el sensor más próximo a ejecutarse) y se lo vuelve a instertar
luego de haberle cambiado su tiempo de próxima ejecución, al final de cada iteración lo que nos representa el heap
es el segmento de tamaño $n$ dentro de la lista ordenda por orden de aparición empezando en el $i$ actual del iterador.
Esto se puede apreciar mejor en el siguiente gráfico.

%% Grafico mostrando el segmento moviendose en cada iteración


De esta forma, cuando se llega a la iteración $k$ el sensor que está en la primera posición del heap es el que se encuentra
en la posición $k$-ésima de lista ordenada por orden de aparición.


\subsection{Pseudoc\'odigo}

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para resolver el problema 2. }
	\label{algo::ej1}
	\begin{algorithmic}
		\Function{ejercicio2}{$n$, $k$, $sensores$}
			\If{$k$ $<$ $n$}
				\State $res \leftarrow sensores[k].indice$
			\Else
				\State \textbf{var} $sensores\_heap \leftarrow crear\_heap(sensores)$
				\State
				
				\For {$i \in [1..k)$}
					\State \textbf{var} $sensor \leftarrow pop\_heap(sensores\_heap)$
					\State $sensor.tiempo \leftarrow sensor.tiempo + sensor.intervalo$
					\State $push\_heap(sensor, sensores\_heap)$
				\EndFor 
				
				\State
				\State $res \leftarrow primero(sensores\_heap).indice$
			\EndIf
		\EndFunction
	\end{algorithmic}
\end{algorithm}

\subsection{An\'alisis de Complejidad}
Podemos dividir el análisis de complejidad en dos partes dependiendo si el valor de $k$ es menor a $n$ o no.

En caso de que $k < n$ sólo se devuelve el índice del $k$-ésimo sensor, es decir, $k$. En este caso la complejidad
es siempre $O(1)$.

Ahora, en el caso que $k >= n$ tenemos que:

\begin{itemize}
	\item Crear el heap con los n sensores. Esto lleva $O(n\;log(n))$.
	\item Iterar $k$ veces dónde por cada iteración tenemos que: \\
		\begin{itemize}
			\item Quitar del heap el próximo sensor. $O(log(n))$.
			\item Una suma. $O(1)$.
			\item Inserta el sensor de nuevo en el heap. $O(log(n)$.
		\end{itemize}
		Esto en total es: $O(k\;log(n))$.
	\item Devolver el índice del $k$-ésimo sensor. $O(1)$.
\end{itemize}

En total tenemos $O(n\;log(n)) + O(k\;log(n)) + O(1)$ que, dado que $k >= n$, nos da $O(k\;log(n))$.


\subsection{Conclusión}

\subsection{Mediciones}

\newpage